# -*- encoding: utf-8 -*-
'''
Filename         :15_threeSum.py
Description      :
Time             :2022/08/09 10:10:55
Author           :daiyizheng
Email            :387942239@qq.com
Version          :1.0
'''

from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        nums.sort()
        for i in range(n):
            low = i+1
            high = n-1
            while low<high:
                three_sum = nums[i] + nums[low] + nums[high]
                if three_sum == 0:
                    cur = [nums[i], nums[low], nums[high]]
                    if cur not in res:
                        res.append(cur)
                    low +=1
                    high-=1
                elif three_sum>0:
                    high-=1
                else:
                    low+=1
        return res